// Copyright Google Inc 2012. Released under the Apache 2.0 license.
library maps;
import 'dart:html' as html;
import 'dart:math';
import 'drawing.dart';

class TileDef implements Hashable {
  static TileDef _empty;
  static TileDef get empty => _empty == null ? _empty = new TileDef() : _empty;
  
  html.ImageElement img;
  bool passable;
  String name;
  
  get hashCode => name.hashCode;
}

// TODO get rid of Tile unless I can think of some special purpose for it
class Tile {
  TileDef def;
  Tile(this.def);
  Tile.empty() {
    def = TileDef.empty;
  }
}

/** Helper class for the A* path finding helper class. */
class AStarNode implements Hashable {
  Point p;
  int pathCost;
  num estimatedRemaining;
  AStarNode previous;
  AStarNode(this.p, this.pathCost, this.estimatedRemaining, this.previous);

  get hashCode => p.hashCode();
  get estimatedCost => pathCost + estimatedRemaining;
}

/** Helper class for A* path finding. */
class AStar {
  Point start, end;
  Board board;
  // Dart doesn't have a heap, and I don't feel like implementing one again.
  // We'll just go O(n**2) rather than O(n log n).
  Map<Point, AStarNode> open;
  Set<Point> closedPoints;
  AStar(this.start, this.end, this.board):
      open = new Map<Point, AStarNode>(),
      closedPoints = new Set<Point>();


  _est(Point a, Point b) => (a.x - b.x).abs() + (a.y - b.y).abs();
  _path(AStarNode n, [list = null]) {
    if (list == null) list = [];
    if (n.previous != null) {
      // Don't put the source point on there.
      _path(n.previous, list);
      list.add(n.p);
    }
    return list;
  }

  run() {
    open[start] = new AStarNode(start, 0, _est(start, end), null);

    var sw = new Stopwatch();
    sw.start();
    while (open.length > 0) {
      AStarNode next = open.values.reduce(null, (a, b) =>
          a == null ? b : b == null ? a :
              a.estimatedCost < b.estimatedCost ? a : b);
      if (next == null) {
        loggy("no path found");
        return [];
      }
      if (next.p == end) {
        // yay, we reached the end
        return _path(next);
      }
      if (sw.elapsedMilliseconds > 4) {
        return _path(next);
      }
      loggy("removing point ${next.p}");
      open.remove(next.p);
      closedPoints.add(next.p);
      for (var a in next.p.adjacents()) {
        if (!board[a].passable) {
          loggy("$a is impassible; ignoring");
          continue;
        }
        if (a.cornerwiseTo(next.p)) {
          var c1 = new Point(a.x, next.p.y);
          var c2 = new Point(next.p.x, a.y);
          if (!board[c1].passable || !board[c2].passable) {
            // only passable if the adjoining cardinals are passable
            continue;
          }
        }
        if (closedPoints.contains(a)) {
          loggy("already looked at $a; ignoring");
          // we already got there by a shorter path
          continue;
        }
        var node = new AStarNode(a, 1 + next.pathCost, _est(a, end), next);
        var existing = open[a];
        if (existing == null || existing.pathCost > node.pathCost) {
          loggy("adding $a to open list");
          open[a] = node;
        } else {
          loggy("already have a good path to $a");
        }
      }
    }
    return []; // no path
  }

  loggy(str) {}
}

class SubBoard implements Hashable {
  Rect rect;
  Set<Rect> rooms;
  Set<SubBoard> connections;
  SubBoard(this.rect):
      rooms = new Set<Rect>(),
      connections = new Set<SubBoard>();
  get hashCode => rect.hashCode;
}

class Board {
  var tiles;
  int w, h;
  Point start, end;
  Set<Rect> rooms;
  Set<SubBoard> subboards;

  Board(this.w, this.h) {
    tiles = [];
    subboards = new Set<SubBoard>();
    subboards.add(new SubBoard(new Rect(new Point(0, 0), new Point(w, h))));
  }

  Point aStar(Point start, Point dest) {
    ////print("a* $start -> $dest");
    if (!this[start].passable) {
      throw new Exception("escape artist");
    }
    if (!this[dest].passable) {
      throw new Exception("intrusion detection");
    }
    if (!inBounds(start)) {
      throw new Exception("off sides");
    }
    if (!inBounds(dest)) {
      throw new Exception("foul");
    }
    var starchild = new AStar(start, dest, this);
    var path = starchild.run();
    ////print("go to ${path}");
    if (path == null || path.length == 0) return null;
    var p = path[0];
    if (!inBounds(p) || !this[p].passable) {
      throw new Exception("Sending you into oblivion... $p");
    }
    return p;
  }

  bool inBounds(point) => (point.x >= 0 && point.x < w
      && point.y >= 0 && point.y < h);

  operator[](point) {
    if (!inBounds(point)) return new Tile.empty();
    return tiles[point.x.toInt()][point.y.toInt()];
  }

  operator[]=(point, tile) {
    tiles[point.x.toInt()][point.y.toInt()] = tile;
  }
}